// 283. 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int lastNone0 = 0;
        int size = (int)nums.size();
        for(int i = 0; i < size; i++)
            if(nums[i] != 0) swap(nums[lastNone0++], nums[i]);
    }
};

// 11. 盛最多水的容器
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0,r=height.size()-1;
        int ans=0;
        while(l<r){
            int area=min(height[l],height[r])*(r-l);
            ans=max(ans,area);
            if(height[l]<=height[r]){
                ++l;
            }
            else{
                --r;
            }
        }
        return ans;
    }
};

// 15. 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>>ans;
        int n=nums.size();
        for(int i=0;i<n-2;i++){
            int x=nums[i];
            if(i&&x==nums[i-1])continue;//跳过重复数字
            if(x+nums[i+1]+nums[i+2]>0)break;//优化一：如果当前数加上最小的两个数都大于 0，直接跳出循环
            if(x+nums[n-2]+nums[n-1]<0)continue;// 优化二：如果当前数加上最大的两个数都小于 0，继续向后遍历
            int j=i+1,k=n-1;
            while(j<k){
                int s=x+nums[j]+nums[k];
                if(s>0){
                    k--;
                }else if(s<0){
                    j++;
                }else{//三数之和为0
                    ans.push_back({x,nums[j],nums[k]});
                    for(j++;j<k&&nums[j]==nums[j-1];j++);// 跳过重复数字
                    for(k--;k>j&&nums[k]==nums[k+1];k--);// 跳过重复数字
                }
            }
        }
        return ans;
    }
};


// 42. 接雨水
class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int left=0,right=height.size()-1;
        int leftMax=0,rightMax=0;
        while(left<right){
            leftMax=max(leftMax,height[left]);
            rightMax=max(rightMax,height[right]);
            if(height[left]<height[right]){
                ans+=leftMax-height[left];//单调递增无水滴
                ++left;
            }else{
                ans+=rightMax-height[right];
                --right;
            }
        }
        return ans;
    }
};

